#include<iostream>
#define SIZE 50
using namespace std;

//城市结点的信息
struct City{
    int num;//城市编号
	double fvalue,gvalue,hvalue;//f值,g值,h值
	int level;//层
	struct City *parent;//父节点
	struct City *next;//后继
	struct City *front;//前驱
};

//表，用于保存路径上的城市结点
class List{
public:
	List();//初始化列表
	struct City *head;
	struct City *tail;
};

List::List()
{
	head=new struct City;
	tail=new struct City;
	head->next=tail;
	tail->front=head;
}

class AStar{
public:
	AStar();//构造函数
	void input();//初始化输入信息
	int get_min_distance();//获取所有路径中最短的路径
    City TspAStar(int start);//从start开始出发计算最佳路径回到start
	void output(City city);//输出最佳路径

private:
	int city_num;//存放城市的数目
	double city_distance[SIZE][SIZE];//城市之间距离的关系矩阵，限制城市的数目不超过50
	int min_distance;//两城市之间的最短距离
	bool path[SIZE];//是否在当前最佳路径上，例path[i]=true,第i+1城市在当前最佳路径上
	double optimal[200];//保存最优解
	int number;//保存迭代的次数
};

AStar::AStar()
{
	input();
	min_distance=get_min_distance();
}

void AStar::input()
{
	int i,j;
	cout<<"请输入城市的数目: ";
	cin>>city_num;
	cout<<"\n请输入城市之间距离的关系矩阵: \n";
	for(i=0;i<city_num;i++)
	{
		path[i]=false;
		for(j=0;j<city_num;j++)
			cin>>city_distance[i][j];
	}
	//判断关系矩阵输入是否有误？
	for(i=0;i<city_num;i++)
	{
		for(j=0;j<i;j++)
			if(city_distance[i][j]!=city_distance[j][i])
			{
				cout<<"\n输入的关系矩阵有误!即将退出……\n";
				exit(-1);
			}
		if(city_distance[i][i]!=0)
		{
			cout<<"\n输入的关系矩阵有误!即将退出……\n";
			exit(-1);
		}
	}
}

int AStar::get_min_distance()
{
	int min=0;
	for(int i=0;i<city_num;i++)
		for(int j=0;j<city_num;j++)
			if(city_distance[i][j]>0)//城市i和j不相同，且存在路径
			{
				if(0==min||min>city_distance[i][j])
					min=city_distance[i][j];
			}
	return min;
}

City AStar::TspAStar(int start)
{
	struct City *p0=new struct City;//构造出发城市结点
	p0->num=start;
	p0->level=0;
	p0->parent=NULL;
	p0->gvalue=0;
	p0->hvalue=min_distance*(city_num-p0->level);
	p0->fvalue=p0->gvalue+p0->hvalue;
    path[start-1]=true;
	struct City *p1,*p2,*p_min;
	List open;
	int count=0;//记录被访问城市结点的数目
    int k=0;
	while(1)
	{
		//cout<<"hehe\n";
		for(int i=0;i<city_num;i++)
			if(path[i])
				count++;
		if(count==city_num)//所有结点都被访问过,即将回到出发点
			path[start-1]=false;

		p1=open.tail->front;
		p2=open.tail;
		for(int i=0;i<city_num;i++)
		{
			if(!path[i])//没有经过的城市结点
			{
				//构造新的城市结点
				struct City *p=new struct City;
				p->level=p0->level+1;
				p->num=i+1;
				p->parent=p0;
				p->gvalue=p0->gvalue+city_distance[p0->num-1][i];
				p->hvalue=min_distance*(city_num-p->level);
				p->fvalue=p->gvalue+p->hvalue;
				//新构造的城市结点插入open表中
				p1->next=p;
				p->front=p1;
				p->next=p2;
				p2->front=p;
				p1=p;
			}
		}
		struct City *p=open.head->next;
		p_min=p;
		while(p!=open.tail)//从open表中寻找f值最小的城市结点
		{
			if(p->fvalue<p_min->fvalue)
				p_min=p;
			p=p->next;
		}
		//**********保存迭代次数和最优值***************************
		optimal[k++]=p_min->gvalue;
		//*********************************************************
		p=p0;//p0是上一次的最优路经点
		while(p)//撤销上一次的路径
		{
			path[p->num-1]=false;
			p=p->parent;
		}
		p=p_min;//新找到的最优路径点
		while(p)//重新配置最优路径
		{
			path[p->num-1]=true;
			p=p->parent;
		}
		p0=p_min;//再次使得p0指向最优路径点，为下一次所用
		//在Open中删除找到的路径点
		p_min->front->next=p_min->next;
		p_min->next->front=p_min->front;
		
		if(p_min->num==start)
			break;
		count=0;
	}
	number=k;
	
	return *p_min;
}

void AStar::output(City city)
{
	struct City *p=&city;
	struct City *p1,*p2;
	List BestPath;

	p1=BestPath.head;
	p2=BestPath.tail;

	while(p!=NULL)//将路径顺序存入Bestpath表中
	{//头插法
		p1->next=p;
		p->front=p1;
		p->next=p2;
		p2->front=p;
		p2=p;

		p=p->parent;
	}
	//输出最优路径
	p=p1->next;
	p2=BestPath.tail;
	while(p!=p2)
	{
		cout<<p->num;
		p=p->next;
		if(p==p2) break;
		cout<<"-->";
	}
	cout<<"\n\n最佳路径上每两个城市的距离为:\n";
    p=p1->next;
	while(p->next!=p2)
	{
		cout<<p->num<<"-->";
		p=p->next;
		cout<<p->num<<" : "
			<<city_distance[p->front->num-1][p->num-1]<<endl;
	}
	cout<<"\n最佳路径的距离为: ";
	cout<<p->fvalue<<endl;

	//*******输出每次迭代的最优解*****
	for(int i=0;i<number;i++)
		cout<<i+1<<": "<<optimal[i]<<endl;
	//********************************
}

void main()
{
	int start=1;//出发城市
	AStar S;
	City city=S.TspAStar(start);
	S.output(city);
}